package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-29 17:17
 **/
public class LeetCode687 {
    int maxEdge = 0;

    public int longestUnivaluePath(TreeNode root) {
        recur(root);
        return maxEdge;
    }

    int recur(TreeNode root) {

        if (root == null) {
            return 0;
        }

        int leftEdge = recur(root.left);
        int rightEdge = recur(root.right);
        int curVal = root.val;

        //返回的左分支相同值路径的最大边数
        int returnLeftEdge = 0;
        //返回的右分支相同值路径的最大边数
        int returnRightEdge = 0;

        if (root.left != null && curVal == root.left.val) {
            returnLeftEdge = leftEdge + 1;
        }

        if (root.right != null && curVal == root.right.val) {
            returnRightEdge = rightEdge + 1;
        }

        maxEdge = Math.max(returnLeftEdge + returnRightEdge, maxEdge);

        return Math.max(returnRightEdge, returnLeftEdge);
    }

}
